Bus Transportation

Memory limit: 32 MB

The mayor of Bytetown is planning to create a bus transportation network. The network will consist of bus stops and bus lines. Two of the bus stops, denoted as and , will be selected as transfer nodes and each of the remaining stops will be directly connected to either or (but not to both of them). Additionally, there will be a bus line connecting both transfer nodes. Due to lack of funds no other bus connections will be created.

The travel distance between two bus stops located at coordinates and that have a direct bus connection equals . If two bus stops are both connected to the same transfer node, the travel distance between them squals the sum of their distances to that transfer node. If two bus stops are connected to different transfer nodes, the travel distance between them equals the sum of their distances to the respective transfer nodes plus the distance between the transfer nodes.

Task

Write a program which:

• reads the locations of bus stops from the input,
• chooses two bus stops as the transfer nodes and selects pairs of bus stops to be connected to each other directly so that the maximum distance between any two bus stops is as small as possible,
• writes the result to the standard output.

Input

The first line of the standard input contains one integer (), the number of bus stops in Bytetown. Each of the following lines contains two positive integers not exceeding , the coordinates of a bus stop. There is at most one bus stop located in each point.

Output

Your program should write to the standard output one integer: the maximum distance between any two bus stops assuming an optimal selection of transfer nodes and connections between pairs of bus stops.

Example

For the input data:

6
1 7
16 6
12 4
4 4
1 1
11 1

the correct result is:

20

The figure corresponds to the sample data. The stops no. 3 and 4 are the transfer nodes.

Task originating from one of the IOI's.